package leetcode_400;

/**
 *@author 周杨
 *RangeSumQuery2DImmutable_304  返回2D矩阵中范围的总和
 *describe:和一维一个思想 AC 50%
 *2018年6月30日 下午12:16:09
 */
public class RangeSumQuery2DImmutable_304 {
	int help[][];
	public static void main(String[] args) {
		int matrix[][]=new int[][] {{3, 0, 1, 4, 2},{5, 6, 3, 2, 1},
			{1, 2, 0, 1, 5},{4, 1, 0, 1, 7},{1, 0, 3, 0, 5}};
		RangeSumQuery2DImmutable_304 test =new RangeSumQuery2DImmutable_304(matrix);

	}
	public RangeSumQuery2DImmutable_304(int[][] matrix) {
		if(matrix.length==0||matrix[0].length==0)
				return ;
	     this.help=new int[matrix.length+1][matrix[0].length+1];
	     for(int row=matrix.length-1;row>=0;row--) {
	    	 for(int col=matrix[0].length-1;col>=0;--col) {
	    		 help[row][col]=matrix[row][col]+help[row+1][col]
	    				 +help[row][col+1]-help[row+1][col+1];
	    	 }
	     }
	}
	    
	public int sumRegion(int row1, int col1, int row2, int col2) {
	        return this.help[row1][col1]-this.help[row1][col2+1]
	        		-this.help[row2+1][col1]+this.help[row2+1][col2+1];
	}
}
